package problem52_NQueens_II;

/**
 * https://zhuanlan.zhihu.com/p/22873368?refer=bittiger
 * 
 * @author john
 *
 */
public class Solution {
	private int count=0;
	
	public int totalNQueens(int n) {
		//shu
        boolean[] verticalLines=new boolean[n];
        //pie
        boolean[] slashes=new boolean[2*n-1];
        //na,
        boolean[] backslashes=new boolean[2*n-1];
        dfs(n,0,verticalLines,slashes,backslashes);
        return count;
    }
	
	private void dfs(int n,int row,boolean[] verticalLines,boolean[] slashes,boolean[] backslashes){
		if(row==n){
			count++;
			return;
		}
		for(int col=0;col<n;col++){
			int verticalLineIndex=col,slashesIndex=row+col,backslashesIndex=n-1+col-row;
			if(verticalLines[verticalLineIndex]||slashes[slashesIndex]||backslashes[backslashesIndex])
				continue;
			verticalLines[verticalLineIndex]=slashes[slashesIndex]=backslashes[backslashesIndex]=true;
			dfs(n,row+1,verticalLines,slashes,backslashes);
			verticalLines[verticalLineIndex]=slashes[slashesIndex]=backslashes[backslashesIndex]=false;
		}
	}
	
	public static void main(String[] args){
		System.out.println(new Solution().totalNQueens(4));
	}
	
}
